This invention relates generally to binary adder circuits, and more particularly, to adder circuits employing some type of parallel structure to handle generated carry bits without a conventional "ripple" carry computation. When two binary numbers are added together, the summation at each bit position produces a sum bit and a carry bit, each of which may be a "1" or a "0". The conventional addition process, whether in binary or decimal notation, involves a series of additions beginning at the right-hand or least-significant ends of the numbers. At the first stage, the two digits are added to produce a sum digit and a possible carry digit. Then, at each succeeding digital stage two digits are added together with the carry digit, if any, from the preceeding stage. This is known as a "ripple" addition process, since a carry digit may propagate from one end of the sum to the other, and each digit of the sum may not be determined until all of the preceeding digits of lesser significance have been determined.
The delay time inherent in performing ripple addition is proportional to the number of stages. Identical adder modules, each having a delay time t, may be used to process each addition stage, and the total processing time will therefore be given by nt, where n is the number of stages to be added. Thus, for example, a 32-bit addition will take twice as long as a 16-bit addition.
It has long been recognized that some form of parallel processing is desirable for high-speed addition circuitry. A process known as pyramid carry addition was described in principle by Morton Nadler in "A High-Speed Electronic Arithmetic Unit for Automatic Computing Machines," Acta Technica (of the Czechoslovak Academy of Science) (1956) pp. 464-78. In accordance with this technique, two n-bit binary numbers to be added are first added in a parallel but bit-by-bit basis by n separate adder modules, to generate n first-stage sum bits and n separate carry bits. In a second stage of the process, each of n/2 identical modules processes two sum bits and two carry bits, producing two second-stage sum bits and a single carry bit. In this manner, the second stage of the addition process reduces the number of carry bits by a factor of two.
Similarly, in third and subsequent stages the number of carry bits is successively reduced by a factor of two, until the final sum is obtained with only one remaining carry bit at the most-significant end. If each stage can be implemented in such a way as to have the same inherent delay time, the total delay time will be proportional to the number of stages, which will be log.sub.2 n for values of n that are powers of two. Clearly the pyramid carry adder represents a substantial advance over ripple carry techniques. However, in some applications of adder circuitry, such as in floating point multiplication, even greater improvements in speed are desired. Accordingly, there is still room for improvement over the basic pyramid carry adder, and the present invention is directed to this end.